Solving 10385 - Duathlon (Ternary search)
[andmenj-acm.git] / 11663 - GrayInc / 11663.cpp
blob066ead68da65e7eb98f2b75d1db19ca945a5462f
1 /*
2 Time limit exceeded!
4 I know the algorithm is fast enough (it's O(m * n)) but the implementation is slow
5 */
6 using namespace std;
7 #include <algorithm>
8 #include <iostream>
9 #include <iterator>
10 #include <sstream>
11 #include <fstream>
12 #include <cassert>
13 #include <climits>
14 #include <cstdlib>
15 #include <cstring>
16 #include <string>
17 #include <cstdio>
18 #include <vector>
19 #include <cmath>
20 #include <queue>
21 #include <deque>
22 #include <stack>
23 #include <list>
24 #include <map>
25 #include <set>
27 template <class T> string toStr(const T &x){ stringstream s; s << x; return s.str(); }
28 template <class T> int toInt(const T &x){ stringstream s; s << x; int r; s >> r; return r; }
30 #define For(i, a, b) for (int i=(a); i<(b); ++i)
31 #define foreach(x, v) for (typeof (v).begin() x = (v).begin(); x != (v).end(); ++x)
32 #define D(x) cout << #x " = " << (x) << endl
34 string next(const string &s);
35 string prev(const string &s);
37 bool looksLike0000(const string &s){
38 for (int i=0; i<s.size(); ++i) if (s[i] != '0') return false;
39 return true;
42 bool looksLike1000(const string &s){
43 return s[0] == '1' && looksLike0000(s.substr(1));
46 string next(const string &s){
47 if (s.size() == 1) return s == "0" ? "1" : "0";
48 string t = s.substr(1);
49 if (s[0] == '0'){
50 if (looksLike1000(t)){
51 return "1" + t;
52 }else{
53 return "0" + next(t);
55 }else{
56 if (looksLike0000(t)){
57 return "0" + t;
58 }else{
59 return "1" + prev(t);
64 string prev(const string &s){
65 if (s.size() == 1) return s == "0" ? "1" : "0";
66 string t = s.substr(1);
67 if (s[0] == '0'){
68 if (looksLike0000(t)){
69 return "1" + t;
70 }else{
71 return "0" + prev(t);
73 }else{
74 if (looksLike1000(t)){
75 return "0" + t;
76 }else{
77 return "1" + next(t);
82 int main(){
83 int m;
84 string s;
85 while (cin >> m >> s && m){
86 while (m--) s = next(s);
87 cout << s << endl;
89 return 0;